280. 摆动排序

280. 摆动排序

// 奇数位要 ≥ 相邻两侧，偶数位要 ≤ 相邻两侧
/**
 Do not return anything, modify nums in-place instead.
 */
function wiggleSort(nums: number[]): void {
  for (let i = 0; i < nums.length - 1; i++) {
    if (
      (i % 2 === 0 && nums[i] > nums[i + 1]) ||
      (i % 2 === 1 && nums[i] < nums[i + 1])
    ) {
      ;[nums[i], nums[i + 1]] = [nums[i + 1], nums[i]]
    }
  }
}

局部交换的全局正确性

这道题的贪心策略非常简单：遍历相邻元素对，如果不满足摆动条件就交换。问题在于——为什么局部交换不会破坏前面已经处理好的约束？

举个例子：假设前两个位置已经满足 nums[0] ≤ nums[1]，现在处理位置 1 和 2。偶数位要求 nums[1] ≥ nums[2]。如果不满足（即 nums[1] < nums[2]），交换它们。

交换后 nums[1] 变得更大，而 nums[0] ≤ nums[1]（原来的）意味着 nums[0] 仍然 ≤ 新的更大的 nums[1]——前面已满足的条件没有被破坏。

奇数位的情况同理。所以一遍扫描足够。

复杂度

O(N) 时间，O(1) 空间。这题的关键不在于复杂度，而在于证明贪心交换不会引入新的破坏——很多时候贪心正确性的论证比代码本身更有价值。

与 324. 摆动排序 II 的区别

这道题（280）只要求相邻满足大小关系即可，允许相等。但 324 要求严格交替（nums[0] < nums[1] > nums[2] < nums[3]...），且不允许相等元素相邻，这就复杂得多——需要先排序再交错放置。